package LeetCodeHot100TopInterview;

public class Q543_TreeMaxPath {
    //一棵二叉树的直径长度是任意两个结点路径长度中的最大值
    //这条路径可能穿过也可能不穿过根结点
    class Info{
        int maxPath;
        int roadLen;

        public Info(int maxPath, int roadLen) {
            this.maxPath = maxPath;
            this.roadLen = roadLen;
        }
    }
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null){
            return 0;
        }
        return process(root).maxPath - 1;
    }

    public Info process(TreeNode root){

        if (root == null){
            return new Info(0, 0);
        }
        int maxPath = 0;
        int roadLen = 0;
        Info leftInfo = process(root.left);
        Info rightInfo = process(root.right);
        maxPath = Math.max(leftInfo.maxPath, rightInfo.maxPath);
        maxPath = Math.max(maxPath, leftInfo.roadLen + rightInfo.roadLen + 1);
        roadLen = Math.max(leftInfo.roadLen, rightInfo.roadLen) + 1;
        return new Info(maxPath, roadLen);
    }

}
